package _2022.hot100._207_课程表;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author： YHSimon
 * @date： 2022-05-12 15:55
 */
public class Solution {
    // bfs 拓扑排序
    public boolean canFinish2(int numCourses,int[][] prerequisites){
        int[] indegrees=new int[numCourses];
        List<List<Integer>>  adjacency=new ArrayList<>();
        //
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            adjacency.add(new ArrayList<>());
        }
        for(int[] cp:prerequisites){
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }

        for(int i=0;i<numCourses;i++){
            if(indegrees[i]==0) queue.add(i);
        }
        while(!queue.isEmpty()){
            int pre=queue.poll();
            numCourses--;
            for(int cur:adjacency.get(pre)){
                if(--indegrees[cur]==0) queue.add(cur);
            }
        }
        return numCourses==0;
    }


    // dfs
    public boolean canFinish(int numCourses,int [][] prerequisites){
        // 构建邻接表
        List<List<Integer>> adjacency =new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            adjacency.add(new ArrayList<>());
        }
        int[] flags=new int[numCourses];
        for(int[] cp:prerequisites){
            adjacency.get(cp[1]).add(cp[0]);
        }
        for(int i=0;i<numCourses;i++){
            if(!dfs(adjacency,flags,i)) return false;
        }
        return true;
    }


    //flag[i]=0表示未访问  -1表示已被其他节点的DFS遍历 1表示已被当前节点的DFS访问
    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if(flags[i]==1) return false;
        if(flags[i]==-1) return true;
        flags[i]=1;
        for(int j:adjacency.get(i)){
            if(!dfs(adjacency, flags, j)) return false;
        }
        flags[i]=-1;
        return true;
    }
}
